package MySort;

public class SqList {
    // 待排序的顺序表的记录集合
    public RecordNode[] list;

    // 顺序表的长度
    public int len;

    // 顺序表的最大的存储空间
    public int maxSize;

    public SqList(int maxSize) {
        list = new RecordNode[maxSize];
        len = 0;
        this.maxSize = maxSize;
    }



    // 在第i个位置之前插入记录
    public void insert(int i, RecordNode x)throws Exception{
        if(len==maxSize){
            throw new Exception("顺序表已经满了");
        }
        if(i<0 || i>len){
            throw new Exception("插入位置不合理");
        }
        for(int j=len; j>i; j--){
            list[j] = list[j-1];
        }
        list[i] = x;
        len++;
    }

    /**
     * 直接插入排序
     */
    public void insertSort(){
        RecordNode p=new RecordNode();
        for(int i=1; i<len; i++){
            // 待插入的目标值
            p = list[i];
            int j;
            // 如果比list[i]要大就往后移动
            for(j=i-1; j>=0; j--){
                if(list[j-1].key > p.key){
                    list[j+1] = list[j];
                }else{
                    break;
                }
            }
            // 如果是一开始就小于直接跳出就相当于不变
            list[j+1]=p;
        }
    }

    /**
     *  希尔排序
     * @param d  传入的增量数组
     */
    public void shellSort(int[] d){
        RecordNode p = new RecordNode();
        for(int i=0; i<d.length; i++){
            int k=d[i];
            for(int j = k; j<len && j<2*k; j++){
                p = list[j];
                int m;
                for(m=j-k; m>=0; m=m-k){
                    if(list[m].key > p.key){
                        list[m+k] = list[m];
                    }else {
                        break;
                    }
                }
                list[m+k]=p;
            }
        }
    }


    /**
     * 冒泡排序基本
     */
    public void bubbleSort(){
        RecordNode p = new RecordNode();
        boolean flag = true;
        for(int i=1; i<len && flag; i++){
            flag = false;
            for(int j=0; j<=len-i-1; j++){
                if(list[j].key > list[j+1].key){
                    p = list[j+1];
                    list[j+1] = list[j];
                    list[j] = p;
                    flag = true;
                }
            }
        }

    }


    /**
     * 冒泡排序优化
     */
    public void bubbleSortBetter(){
        RecordNode p = new RecordNode();
        // 定义数据最后移动的下标位置，以及判断冒泡结束的标志
        int exchange = len-1;
        while(exchange !=0){
            // 定义需要无序曲的最后下标
            int bound = exchange;
            // 每次重置最后移动的下标
            exchange = 0;
            for(int j=0; j<bound; j++){
                if(list[j].key > list[j+1].key){
                    // 如果 后比前大 置换位置
                    p = list[j+1];
                    list[j+1] = list[j];
                    list[j] = p;
                    exchange = j;
                }
            }
        }
    }


    /**
     * 快速排序
     * @param low 待排序最小下标
     * @param high 待排序的最大下标
     */
    public void qSort(int low, int high){
        if(low < high){
            int p = Partition(low, high);
            qSort(low, p-1);
            qSort(p+1, high);
        }
    }

    /**
     * 快速排序的划分过程
     * @param low  待划分数组最小下标
     * @param high 待划分数组的最大下标
     * @return 划分完成后的 中间值的下标
     */
    public int Partition(int low, int high){
        // 选取第一个元素 作为比较的数据元素点，以此来进行排序
        RecordNode p = list[low];
        // 开始交替扫描数组
        while(low<high){
            while(low<high && list[high].key > p.key){
                high--;
            }
            if(low<high){
                // 交换值
                list[low] = list[high];
                low++;
            }
            while (low<high && list[low].key<p.key){
                low++;
            }
            if(low < high){
                list[high] = list[low];
                high--;
            }
        }
        // 此时2边都已经排好顺序了，此时low指的位置的值应该是 比较元素的值 所以讲low赋予p
        list[low]=p;
        return low;
    }

    /**
     * 直接选择排序
     */
    public void selectSort(){
        RecordNode p = new RecordNode();
        for(int i=0; i<len-1; i++){
            // 优先默认初始值的数据为最小的数据
            int min=i;
            // i后面的数据为 无序区数据，开始遍历
            for(int j=i; j<len; j++){
                // 如果 i.key > j.key 说明j位置上的数据是最小的所以将 min 换成最小
                if(list[i].key > list[j].key){
                    min = j;
                }
            }
            // 如果 min != i 说明这个最小值发生了变化 需要将最小的值与i的值对换
            if(min!=i){
                p = list[i];
                list[i] = list[min];
                list[min] = p;
            }
        }
    }


    /** 堆排序的前置算法
     * 构建大根堆的下沉算法 （这里树的结点从 0--[len-1], 所以左子树 2i+1  右子树 2i+2  父节点 i/2-1 ）
     * @param low 待下沉的结点序号
     * @param high 无序区的最后一个节点序号
     */
    public void sift(int low, int high){
        int i = low;
        // 左子树
        int j = 2*i+1;
        // 遍历待排序结点，是待排序结点下的所有子树必然处于大根堆
        while(i<high) {
            RecordNode p = list[i];
            // j<high 判断这个结点是否存在右子树
            // 后面左右结点比较，待排序结点只与最大值发生交换完成大根堆的构建
            if (j < high && list[j].key > list[j + 1].key) {
                j++;
            }
            if (p.key < list[j].key) {
                // 发生位置交换
                list[i] = list[j];
                list[j] = p;
                // 开始比较
                i = j;
                j = 2 * i + 1;
            } else {
                // 没有发生置换 就不需要继续向下遍历
                i = high + 1;
            }
        }
    }

    /**
     * 堆排序
     */
    public void heapSort(){
        RecordNode p = new RecordNode();
        // 首次构建大根堆
        // (len/2-1)  最底层结点的父节点， 此时开始堆排序（需要待排序结点的子节点都是大根堆，所以需要从最底层开始往外进行大根堆构建）
        for(int i=len/2-1; i>=0; i--){
            sift(i, len-1);
        }

        // 筛选法调整堆 每次都会从无序区选择一个进入有序区，最后使无序区无数据
        for(int i=len-1; i>0; i--){
            p = list[0];
            list[0] = list[i];
            list[i] = p;
            // i-1  因为上面交换的操作使有序区增长的一个
            sift(0, i-1);
        }
    }

    /** 归并排序前置算法
     * 2个数组进行有序合并
     * @param order 最后排序的数组
     * @param a 数组
     * @param i 第一个数组的起始点
     * @param k 第一个数组的截止点 k+1第二个数组的起始点
     * @param j 第二个数组的截止点
     */
    public void merge(RecordNode[] order, RecordNode[] a, int i, int k, int j){
        int t=i;
        // 第一个数组起始元素
        int m=i;
        // 第二个数组起始元素
        int n = k+1;
        // 第一个数组
        for(; m<=k; ){
            // 第二个数组
            for(; n<=j;){
                // 开始替换数据
                if(a[m].key <= a[n].key){
                    // 这里第一个数组比较小 放入order中
                    order[t]=a[m];
                    t++;
                    m++;
                }else{
                    // 这里第二个数组比较小放入order中
                    order[t]=a[n];
                    t++;
                    n++;
                }
            }
        }
        // m<=k 代表第二个数组已经放完了，但是第一个数组还没有放完
        while(m<=k){
            order[t] = a[m];
            t++;
            m++;
        }

        // n<=j 代表第一个已经放完了，但是第二个数组还没有放完
        while(n<=j){
            order[t] = a[n];
            t++;
            n++;
        }
    }

    /** 归并排序前置算法
     * 一趟归并排序 将有序列表22合并 并且最终结果放在数组order中
     * @param order 已经排序好的数组
     * @param a 数组
     * @param s 待排序数组长度
     * @param n 数组长度
     */
    public void mergePass(RecordNode[] order, RecordNode[] a, int s, int n){
        int p = 0;

        // 两两规并 长度均为s的有序表
        while(p+2*s-1 <= n-1){
            merge(order, a, p, p+s-1, p+2*s-1);
            p = p+2*s;
        }
        // 归并长度不相等的有序表
        if(p+s-1<n-1){
            merge(order, a, p, p+s-1, n-1);
        }else{
            for(int i=p; i<=n-1; i++){
                order[i] = a[i];
            }
        }
    }

    public void mergeSort(){
        // 已经排序的子序列长度 初始值为1
        int s = 1;
        RecordNode order[] = new RecordNode[len];
        while(s<len){
            mergePass(order, list, s, len);
            s = s*2;
            mergePass(list, order, s, len);
            s = s*2;
        }


    }

}

